In conventional computer systems, images are displayed on a two-dimensional screen. The images are defined by arrays of pixels which are either stored in computer memory or received from sources connected to the computer system.
Many images of physical objects may be defined three-dimensionally and may be stored or received as three-dimensional raw data arrays. In recent years, efforts have been undertaken to utilize three-dimensional raw data to take into account the distance and various characteristics of objects within screen images. One of the problems associated with the generation and display of such screen images is the size and complexity of circuitry and logic currently required to produce a stream of screen image data in the order required by a display. Various techniques have been developed to produce the screen data stream utilizing multi-stage graphics computer systems.
One of the graphics computer systems which have been developed to produce the screen data stream is shown in FIG. 1A. Graphics computer system 101 may be implemented with a conventional X86 (such as the 400 series) IBM-compatible or MacIntosh personal computer or a graphics engine that includes application unit 103 which generates geometries that are to be rendered. The output of application unit 103 is a stream of geometry data characterized in three-dimensional space. Transformation unit 105 transforms the geometry data from three-dimensional spatial coordinates to two-dimensional display coordinates corresponding to the screen plane. Transformation unit 105 also reformats the geometry data into a more unified format. For example, transformation unit 105 may accept as input independent polygons, quad strips, concave polygons and higher and only output triangle strips. The output of transformation unit 105 includes graphics primitives readable by rasterizer 107 in display coordinates. Rasterizer 107 receives the graphics primitives and converts them to pixels which in turn are transmitted to display 109 to generate a screen image.
Another graphics computer systems which has been developed to produce the screen data stream is shown in FIG. 1B. Graphics computer system 151 is shown which includes frame buffer 111. Frame buffer 111 is utilized by system 151 to decouple the rendering process from a video refresh rate. This permits the image undergoing rendering to be updated at a slower rate than the screen image shown on display 109 is refreshed. Some implementations of rasterizers 107 require associated frame buffers 111 to reorder pixels into screen refresh order. The output of frame buffer 111, or rasterizer 107 if no frame buffer 111 exists, is a stream of pixels, where each pixel contains one color associated with one screen pixel.
With reference to FIG. 2A, conventional rasterizer 107 is shown which outputs pixels in polygon order. The conventional rasterizer includes slope, vertical, horizontal slope, and horizontal processing units designated as delta calculation, vertical interpolate, horizontal delta calc, and horizontal interpolation units 203, 205, 207, 209, respectively.
An example of triangle primitives rasterized by rasterizer 107 are shown in FIG. 2B. The triangles are type classified as: top, bottom, left, and right facing triangles 253, 255, 257, 259.
Conventionally, rasterizing occurs in three steps. The first rasterizing step converts the three point format of the triangle into three edges. The edges are usually described in the form of By+C. The second rasterizing step evaluates points along the edges of the triangle. There are two interpolators utilized in the second step, one for the left edge and one for the right edge. The output of the interpolator are referred to as spans, which are horizontal lines defined by a y-value, left and right x-values and any other parameters of the polygon defined at the ends of the span. The third rasterizing step also utilizes an interpolator which accepts a span and outputs the pixels that the span defines. For each pixel, the interpolator outputs the y-value and x-value of the current pixel and the value of the parameters of each pixel.
Graphics computer systems 151 utilizing such conventional rasterizers 107 require frame buffer 111 to reorder the pixels into the order needed by display 109 and also require a color unit to determine which pixel is visible and carries the color to be utilized by the associated screen pixel. Software applying the painters' algorithm provide a simple process to perform this task, which follows the rule that the last pixel sent to a pixel in frame buffer 111 replaces the pixel stored within frame buffer 111. However, in order to perform this operation, the polygon data sent to rasterizer 107 must be sorted from back-to-front.
Conventional hardware, such as SGI-GTX manufactured by Silicon Graphics, Inc., that does not require back-to-front sorting applies a z-buffer algorithm. Z-buffer algorithms utilize an additional buffer, referred to as the z-buffer, that stores range values (z-values) as described by K. Akeley and T. Jermoluk in "High-Performance Polygon Rendering", SIGGRAPH 88, 239-246. The pixel currently stored in frame buffer 111 and z-buffer is read by rasterizer 107 and the z-values of the new pixel and the pixel in frame buffer 111 are compared by rasterizer 107. If the new pixel is in front of the pixel in frame buffer 111 then the new pixel replaces the pixel in frame buffer 111, otherwise the new pixel is discarded. Some algorithms that determine the color of a screen pixel require information about more than just the frontmost polygon that intersects a screen pixel. Examples of cases where information about multiple polygons is needed include: anti-aliasing, CSG (constructional solid geometry), and transparency. One solution is to modify frame buffer 111 to hold a list of pixels at each point and after all polygons have been rendered process the list of rendered pixels at each screen pixel into a single color.
Other work has been done to modify graphics computer systems which use z-buffers to provide some of the features of the multiple pixel/screen pixel system without the cost of the memory needed by the multiple pixel/screen pixel system, for example by drawing the polygons in front-to-back or back-to-front order.
Rasterizers 107 that operate on data in polygon order are efficient, since a single interpolator rasterizes multiple polygons and, as long as there are polygons to be rasterized, the interpolator can be rendering. One of the disadvantages is that the pixels are not output in raster order and need to be reordered by frame buffer 111. Additionally, since the pixels are output in polygon order, it is impossible to merge pixels from different polygons into a single screen pixel before the pixels are written into frame buffer 111 as a result the bandwidth needed into frame buffer 111 is very high. Another disadvantage is that if the color algorithm requires information about more than one rasterized pixel in each screen pixel either a very large frame buffer must be used or the polygons must be presorted, and presorted does not work in all cases.
A technique used to produce and transmit pixels in raster order is implemented with processor per primitive architecture 301 as partially shown in FIG. 3. Processor architecture 301 includes array 303 of n processor-interpolator pairs. Each processor-interpolator pair of array 303 renders one polygon over the entire screen. The interpolators used in a processor per primitive are similar to those interpolators used in the polygon order system except that since the pixels are output in raster order there is no need to output the coordinate of each pixel. Instead, there is a need to indicate whether or not a given polygon intersects the current pixel. This can be done by comparing the y-values (vertical coordinate) of the current pixels against the top and bottom of the triangle and the x-values (horizontal coordinate) of the current pixels against the left and right edges of the span at the current y-value. The outputs of the interpolators of array 303 are connected to bus 305. The output data of the respective interpolators is merged into a single stream by selecting one of the interpolators that has a polygon that intersects the current pixel during each clock cycle and transmitting the pixel that the selected interpolator has generated, where a clock cycle is defined by the processor to coordinate transfers of data. During the following clock cycle, a next interpolator pixel is transmitted, and so on until all the active interpolators for the current screen pixel have transmitted their respectively generated pixels. Once an entire screen of pixels has been generated and transmitted, the interpolators then generate and transmit the associated screen pixels for a next screen and so forth. A method of merging pixels that may be applied with processor per primitive architecture 301 is to use several z-value compare units to determine which interpolator has generated the frontmost screen pixel and to enable the interpolator with the frontmost screen pixel to transmit the screen pixel data. Disadvantages of processor per primitive architecture 301 include the large size of each interpolator processor, the large number of interpolator processors required, and low efficiency. Methods to reduce some of the disadvantages include: presorting the polygons from top-to-bottom, designing architecture 301 with the least number of processors required for the most complex scanline, loading the processors from the top of the list of polygons and, as the current scan line moves below the bottom of a polygon loaded into a processor, removing the polygon from the processor to free up space for a new polygon to be read from the list of polygons. Despite these improvements, efficient utilization of processor resources is low and the number of processors needed is high. Therefore, there continues to be a need for a more efficient and compact architecture.